package com.lry.basic.algorithm.tree;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */


public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(6);
        root.right.right = new TreeNode(7);

        TreeNode node = solution.deleteNode(root,3);
        System.out.println(node);
    }

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if(null==root){
            return null;
        }

        if(root.val>key){
            root.left = deleteNode(root.left,key);
            return root;
        }else if(root.val<key){
            root.right = deleteNode(root.right,key);;
            return root;
        }else{
            if(null==root.left){
                return root.right;
            }else if(null==root.right){
                return root.left;
            }else{
                //找右子树的最小节点
                TreeNode min = deleteMin(root);
                min.left = root.left;
                min.right = root.right;
                return min;
            }
        }
    }

    private TreeNode deleteMin(TreeNode node){
        if(node.right.left==null){
            TreeNode res = node.right;
            node.right = null;
            return res;
        }

        return min(node.right);
    }

    private TreeNode min(TreeNode node){
        TreeNode pre = node;
        TreeNode min = node.left;
        while(null!=min&&min.left!=null){
            pre = min;
            min = min.left;
        }
        pre.left = null;
        return min;
    }
}